package leetcode.editor.cn;

//运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。 
//
// 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。 
//写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在
//写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。 
//
// 
//
// 进阶: 
//
// 你是否可以在 O(1) 时间复杂度内完成这两种操作？ 
//
// 
//
// 示例: 
//
// LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
//
//cache.put(1, 1);
//cache.put(2, 2);
//cache.get(1);       // 返回  1
//cache.put(3, 3);    // 该操作会使得关键字 2 作废
//cache.get(2);       // 返回 -1 (未找到)
//cache.put(4, 4);    // 该操作会使得关键字 1 作废
//cache.get(1);       // 返回 -1 (未找到)
//cache.get(3);       // 返回  3
//cache.get(4);       // 返回  4
// 
// Related Topics 设计

import lombok.val;

import java.util.HashMap;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Map;

public class LruCache{
    public static void main(String[] args) {

    }

//leetcode submit region begin(Prohibit modification and deletion)
class LRUCache {
    private int capacity;
    private int size;
    private Map<Integer,Node> map;
    Node dummyHead;
    Node dummyTail;


    class Node{
        int key;
        int val;
        Node pre ;
        Node next ;
        public Node(){

        }
        public Node(int key,int val){
            this.val = val;
            this.key = key;
        }
    }

    LRUCache(int capacity){
        this.capacity = capacity;
        this.size = 0;
        this.map = new HashMap<>();
        this.dummyHead = new Node();
        this.dummyTail = new Node();
        this.dummyHead.next = this.dummyTail;
        this.dummyTail.pre = this.dummyHead;
    }

    void removeNode(Node node){
        Node tempForPre = node.pre;
        Node tempForNext = node.next;
        //node的前节点的next = node的后节点
        tempForPre.next = tempForNext;
        //node的后节点的pre = node的前节点
        tempForNext.pre = tempForPre;
    }

    void addToHead(Node node){
        node.next = this.dummyHead.next;
        node.pre = this.dummyHead;
        this.dummyHead.next.pre = node;
        this.dummyHead.next = node;
    }

    Node removeTail(){
        Node deleteNode = this.dummyTail.pre;
        removeNode(this.dummyTail.pre);
        return deleteNode;
    }

    void moveNodeToHead(Node node){
        removeNode(node);
        addToHead(node);
    }

    void put(int key,int val){
        Node node = map.get(key);
        if(node != null){
            node.val = val;
            moveNodeToHead(node);
        }else{
            size ++;
            if(size > capacity){
                Node n = removeTail();
                map.remove(n.key);
                size-- ;
            }
            Node newNode = new Node(key,val);
            map.put(key,newNode);
            addToHead(newNode);
        }
    }

    int get(int key){
        Node node = map.get(key);
        if(node != null){
            moveNodeToHead(node);
            return node.val;
        }else{
            return -1;
        }
    }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)
}